package com.practice.string;

/**
 * Given a string, are all characters unique?
 */
public class UniqueChar {
	/**
	 * O(n^2) solution, no space needed.
	 * 
	 * @param string
	 * @return
	 */
	public boolean areUniqueChars(String string) {
		char[] c = string.toCharArray();
		for (int i=0; i<c.length; i++) {
			for (int j=i+1; j<c.length; j++) {
				if (c[i] == c[j]) return false;
			}
		}
		return true;
	}
	
	/**
	 * Assumption: lower-case string.
	 * 
	 * @param string
	 * @return
	 */
	public boolean areUniqueChars2(String string) {
		char[] c = string.toCharArray();
		int hash = 0;
		for (int i=0; i<c.length; i++) {
			int bit = 1 << (c[i] - 'a');
			if ((hash & bit) > 0) return false;
			hash |= bit; 
		}
		return true;
	}
}
